Language/OS - Multiplatform Resource Library/LANGUAGE OS.iso/scm/slib_inf.lha/slib.info-2

GNU Info File | 1993-05-16 | 41KB | 963 lines

This is Info file slib.info, produced by Makeinfo-1.49 from the input
file slib.texi.
  This file documents SLIB, the portable Scheme library.
  Copyright (C) 1993 Todd R. Eigenschink
  Permission is granted to make and distribute verbatim copies of this
manual provided the copyright notice and this permission notice are
preserved on all copies.
  Permission is granted to copy and distribute modified versions of this
manual under the conditions for verbatim copying, provided that the
entire resulting derived work is distributed under the terms of a
permission notice identical to this one.
  Permission is granted to copy and distribute translations of this
manual into another language, under the above conditions for modified
versions, except that this permission notice may be stated in a
translation approved by the author.
File: slib.info,  Node: Syntactic Closures,  Next: Syntax-Case Macros,  Prev: Macros That Work,  Up: Macro Implementations
Syntactic Closures
==================
  `(require 'syntactic-closures)'
  Syntactic-closure macros.
 -- Function: macro:expand EXPRESSION
     Returns scheme code with the macros and derived expression types of
     EXPRESSION expanded to primitive expression types.
 -- Function: macro:eval EXPRESSION
     `macro:eval' returns the value of EXPRESSION in the current top
     level environment.  EXPRESSION can contain macro definitions. Side
     effects of EXPRESSION will affect the top level environment.
 -- Function: macro:load FILENAME
     FILENAME should be a string.  If filename names an existing file,
     the `macro:load' procedure reads Scheme source code expressions and
     definitions from the file and evaluates them sequentially.  These
     source code expressions and definitions may contain macro
     definitions. The `macro:load' procedure does not affect the values
     returned by `current-input-port' and `current-output-port'.
Syntactic Closure Macro Facility
--------------------------------
                  A Syntactic Closures Macro Facility
                            by Chris Hanson
                            9 November 1991
  This document describes "syntactic closures", a low-level macro
facility for the Scheme programming language.  The facility is an
alternative to the low-level macro facility described in the `Revised^4
Report on Scheme.' This document is an addendum to that report.
  The syntactic closures facility extends the BNF rule for TRANSFORMER
SPEC to allow a new keyword that introduces a low-level macro
transformer:
     TRANSFORMER SPEC := (transformer EXPRESSION)
  Additionally, the following procedures are added:
     make-syntactic-closure
     capture-syntactic-environment
     identifier?
     identifier=?
  The description of the facility is divided into three parts.  The
first part defines basic terminology.  The second part describes how
macro transformers are defined.  The third part describes the use of
"identifiers", which extend the syntactic closure mechanism to be
compatible with `syntax-rules'.
Terminology
...........
  This section defines the concepts and data types used by the syntactic
closures facility.
   * "Forms" are the syntactic entities out of which programs are
     recursively constructed.  A form is any expression, any
     definition, any syntactic keyword, or any syntactic closure.  The
     variable name that appears in a `set!' special form is also a
     form.  Examples of forms:
          17
          #t
          car
          (+ x 4)
          (lambda (x) x)
          (define pi 3.14159)
          if
          define
   * An "alias" is an alternate name for a given symbol.  It can appear
     anywhere in a form that the symbol could be used, and when quoted
     it is replaced by the symbol; however, it does not satisfy the
     predicate `symbol?'.  Macro transformers rarely distinguish
     symbols from aliases, referring to both as identifiers.
   * A "syntactic" environment maps identifiers to their meanings.
     More precisely, it determines whether an identifier is a syntactic
     keyword or a variable.  If it is a keyword, the meaning is an
     interpretation for the form in which that keyword appears.  If it
     is a variable, the meaning identifies which binding of that
     variable is referenced.  In short, syntactic environments contain
     all of the contextual information necessary for interpreting the
     meaning of a particular form.
   * A "syntactic closure" consists of a form, a syntactic environment,
     and a list of identifiers.  All identifiers in the form take their
     meaning from the syntactic environment, except those in the given
     list.  The identifiers in the list are to have their meanings
     determined later.  A syntactic closure may be used in any context
     in which its form could have been used.  Since a syntactic closure
     is also a form, it may not be used in contexts where a form would
     be illegal. For example, a form may not appear as a clause in the
     cond special form. A syntactic closure appearing in a quoted
     structure is replaced by its form.
Transformer Definition
......................
  This section describes the `transformer' special form and the
procedures `make-syntactic-closure' and `capture-syntactic-environment'.
 -- Syntax: transformer EXPRESSION
     Syntax: It is an error if this syntax occurs except as a
     TRANSFORMER SPEC.
     Semantics: The EXPRESSION is evaluated in the standard transformer
     environment to yield a macro transformer as described below.  This
     macro transformer is bound to a macro keyword by the special form
     in which the `transformer' expression appears (for example,
     `let-syntax').
     A "macro transformer" is a procedure that takes two arguments, a
     form and a syntactic environment, and returns a new form.  The
     first argument, the "input form", is the form in which the macro
     keyword occurred.  The second argument, the "usage environment",
     is the syntactic environment in which the input form occurred.
     The result of the transformer, the "output form", is automatically
     closed in the "transformer environment", which is the syntactic
     environment in which the `transformer' expression occurred.
     For example, here is a definition of a push macro using
     `syntax-rules':
          (define-syntax  push
            (syntax-rules ()
              ((push item list)
               (set! list (cons item list)))))
     Here is an equivalent definition using `transformer':
          (define-syntax push
            (transformer
             (lambda (exp env)
               (let ((item
                  (make-syntactic-closure env '() (cadr exp)))
                 (list
                  (make-syntactic-closure env '() (caddr exp))))
                 `(set! ,list (cons ,item ,list))))))
     In this example, the identifiers `set!' and `cons' are closed in
     the transformer environment, and thus will not be affected by the
     meanings of those identifiers in the usage environment `env'.
     Some macros may be non-hygienic by design.  For example, the
     following defines a loop macro that implicitly binds `exit' to an
     escape procedure.  The binding of `exit' is intended to capture
     free references to `exit' in the body of the loop, so `exit' must
     be left free when the body is closed:
          (define-syntax loop
            (transformer
             (lambda (exp env)
               (let ((body (cdr exp)))
                 `(call-with-current-continuation
               (lambda (exit)
                 (let f ()
                   ,@(map (lambda  (exp)
                         (make-syntactic-closure env '(exit)
                                     exp))
                       body)
                   (f))))))))
     To assign meanings to the identifiers in a form, use
     `make-syntactic-closure' to close the form in a syntactic
     environment.
 -- Function: make-syntactic-closure ENVIRONMENT FREE-NAMES FORM
     ENVIRONMENT must be a syntactic environment, FREE-NAMES must be a
     list of identifiers, and FORM must be a form.
     `make-syntactic-closure' constructs and returns a syntactic closure
     of FORM in ENVIRONMENT, which can be used anywhere that FORM could
     have been used.  All the identifiers used in FORM, except those
     explicitly excepted by FREE-NAMES, obtain their meanings from
     ENVIRONMENT.
     Here is an example where FREE-NAMES is something other than the
     empty list.  It is instructive to compare the use of FREE-NAMES in
     this example with its use in the `loop' example above: the examples
     are similar except for the source of the identifier being left
     free.
          (define-syntax let1
            (transformer
             (lambda (exp env)
               (let ((id (cadr exp))
                 (init (caddr exp))
                 (exp (cadddr exp)))
                 `((lambda (,id)
                 ,(make-syntactic-closure env (list id) exp))
               ,(make-syntactic-closure env '() init))))))
     `let1' is a simplified version of `let' that only binds a single
     identifier, and whose body consists of a single expression.  When
     the body expression is syntactically closed in its original
     syntactic environment, the identifier that is to be bound by
     `let1' must be left free, so that it can be properly captured by
     the `lambda' in the output form.
     To obtain a syntactic environment other than the usage
     environment, use `capture-syntactic-environment'.
 -- Function: capture-syntactic-environment PROCEDURE
     `capture-syntactic-environment' returns a form that will, when
     transformed, call PROCEDURE on the current syntactic environment.
     PROCEDURE should compute and return a new form to be transformed,
     in that same syntactic environment, in place of the form.
     An example will make this clear.  Suppose we wanted to define a
     simple `loop-until' keyword equivalent to
          (define-syntax loop-until
            (syntax-rules ()
              ((loop-until id init test return step)
               (letrec ((loop
                     (lambda (id)
                   (if test return (loop step)))))
                 (loop init)))))
     The following attempt at defining `loop-until' has a subtle bug:
          (define-syntax loop-until
            (transformer
             (lambda (exp env)
               (let ((id (cadr exp))
                 (init (caddr exp))
                 (test (cadddr exp))
                 (return (cadddr (cdr exp)))
                 (step (cadddr (cddr exp)))
                 (close
                  (lambda (exp free)
                    (make-syntactic-closure env free exp))))
                 `(letrec ((loop
                    (lambda (,id)
                      (if ,(close test (list id))
                      ,(close return (list id))
                      (loop ,(close step (list id)))))))
                (loop ,(close init '())))))))
     This definition appears to take all of the proper precautions to
     prevent unintended captures.  It carefully closes the
     subexpressions in their original syntactic environment and it
     leaves the `id' identifier free in the `test', `return', and
     `step' expressions, so that it will be captured by the binding
     introduced by the `lambda' expression.  Unfortunately it uses the
     identifiers `if' and `loop' within that `lambda' expression, so if
     the user of `loop-until' just happens to use, say, `if' for the
     identifier, it will be inadvertently captured.
     The syntactic environment that `if' and `loop' want to be exposed
     to is the one just outside the `lambda' expression: before the
     user's identifier is added to the syntactic environment, but after
     the identifier loop has been added.
     `capture-syntactic-environment' captures exactly that environment
     as follows:
          (define-syntax loop-until
            (transformer
             (lambda (exp env)
               (let ((id (cadr exp))
                 (init (caddr exp))
                 (test (cadddr exp))
                 (return (cadddr (cdr exp)))
                 (step (cadddr (cddr exp)))
                 (close
                  (lambda (exp free)
                    (make-syntactic-closure env free exp))))
                 `(letrec ((loop
                    ,(capture-syntactic-environment
                      (lambda (env)
                        `(lambda (,id)
                       (,(make-syntactic-closure env '() `if)
                        ,(close test (list id))
                        ,(close return (list id))
                        (,(make-syntactic-closure env '()
                                      `loop)
                         ,(close step (list id)))))))))
                (loop ,(close init '())))))))
     In this case, having captured the desired syntactic environment,
     it is convenient to construct syntactic closures of the
     identifiers `if' and the `loop' and use them in the body of the
     `lambda'.
     A common use of `capture-syntactic-environment' is to get the
     transformer environment of a macro transformer:
          (transformer
           (lambda (exp env)
             (capture-syntactic-environment
              (lambda (transformer-env)
                ...))))
Identifiers
...........
  This section describes the procedures that create and manipulate
identifiers.  Previous syntactic closure proposals did not have an
identifier data type -- they just used symbols.  The identifier data
type extends the syntactic closures facility to be compatible with the
high-level `syntax-rules' facility.
  As discussed earlier, an identifier is either a symbol or an "alias".
 An alias is implemented as a syntactic closure whose "form" is an
identifier:
     (make-syntactic-closure env '() 'a)
        => an "alias"
  Aliases are implemented as syntactic closures because they behave just
like syntactic closures most of the time.  The difference is that an
alias may be bound to a new value (for example by `lambda' or
`let-syntax'); other syntactic closures may not be used this way. If an
alias is bound, then within the scope of that binding it is looked up
in the syntactic environment just like any other identifier.
  Aliases are used in the implementation of the high-level facility
`syntax-rules'.  A macro transformer created by `syntax-rules' uses a
template to generate its output form, substituting subforms of the
input form into the template.  In a syntactic closures implementation,
all of the symbols in the template are replaced by aliases closed in
the transformer environment, while the output form itself is closed in
the usage environment.  This guarantees that the macro transformation
is hygienic, without requiring the transformer to know the syntactic
roles of the substituted input subforms.
 -- Function: identifier? OBJECT
     Returns `#t' if OBJECT is an identifier, otherwise returns `#f'.
     Examples:
          (identifier? 'a)
             => #t
          (identifier? (make-syntactic-closure env '() 'a))
             => #t
          (identifier? "a")
             => #f
          (identifier? #\a)
             => #f
          (identifier? 97)
             => #f
          (identifier? #f)
             => #f
          (identifier? '(a))
             => #f
          (identifier? '#(a))
             => #f
     The predicate `eq?' is used to determine if two identifers are
     "the same".  Thus `eq?' can be used to compare identifiers exactly
     as it would be used to compare symbols.  Often, though, it is
     useful to know whether two identifiers "mean the same thing".  For
     example, the `cond' macro uses the symbol `else' to identify the
     final clause in the conditional.  A macro transformer for `cond'
     cannot just look for the symbol `else', because the `cond' form
     might be the output of another macro transformer that replaced the
     symbol `else' with an alias.  Instead the transformer must look
     for an identifier that "means the same thing" in the usage
     environment as the symbol `else' means in the transformer
     environment.
 -- Function: identifier=? ENVIRONMENT1 IDENTIFIER1 ENVIRONMENT2
          IDENTIFIER2
     ENVIRONMENT1 and ENVIRONMENT2 must be syntactic environments, and
     IDENTIFIER1 and IDENTIFIER2 must be identifiers.  `identifier=?'
     returns `#t' if the meaning of IDENTIFIER1 in ENVIRONMENT1 is the
     same as that of IDENTIFIER2 in ENVIRONMENT2, otherwise it returns
     `#f'. Examples:
          (let-syntax
              ((foo
                (transformer
                 (lambda (form env)
               (capture-syntactic-environment
                (lambda (transformer-env)
                  (identifier=? transformer-env 'x env 'x)))))))
            (list (foo)
              (let ((x 3))
                (foo))))
             => (#t #f)
          (let-syntax ((bar foo))
            (let-syntax
                ((foo
              (transformer
               (lambda (form env)
                 (capture-syntactic-environment
                  (lambda (transformer-env)
                    (identifier=? transformer-env 'foo
                          env (cadr form))))))))
              (list (foo foo)
                (foobar))))
             => (#f #t)
Acknowledgements
................
  The syntactic closures facility was invented by Alan Bawden and
Jonathan Rees.  The use of aliases to implement `syntax-rules' was
invented by Alan Bawden (who prefers to call them "synthetic names").
Much of this proposal is derived from an earlier proposal by Alan
Bawden.
File: slib.info,  Node: Syntax-Case Macros,  Prev: Syntactic Closures,  Up: Macro Implementations
Syntax-Case Macros
==================
  `(require 'syntax-case)'
  This is version 2.1 of `syntax-case', the low-level macro facility
proposed and implemented by Robert Hieb and R. Kent Dybvig.
  This version is further adapted by Harald Hanche-Olsen
<[e-mail]> to make it compatible with, and easily usable
with, SLIB.  Mainly, these adaptations consisted of:
   * Removing white space from `expand.pp' to save space in the
     distribution.  This file is not meant for human readers anyway...
   * Removed a couple of Chez scheme dependencies.
   * Renamed global variables used to minimize the possibility of name
     conflicts.
   * Adding an SLIB-specific initialization file.
   * Removing a couple extra files, most notably the documentation (but
     see below).
  If you wish, you can see exactly what changes were done by reading the
shell script in the file `syncase.sh'.
  The two PostScript files were omitted in order to not burden the SLIB
distribution with them.  If you do intend to use `syntax-case',
however, you should get these files and print them out on a PostScript
printer.  They are available with the original `syntax-case'
distribution by anonymous FTP in
`cs.indiana.edu:/pub/scheme/syntax-case'.
  To load syntax-case, execute:
     (require 'syntax-case)
     (require 'repl)
     (repl:top-level macro:eval)
  To check your sanity, run
     (syncase:sanity-check)
  Beware that `syntax-case' takes a long time to load -- about 20s on a
SPARCstation SLC (with SCM) and about 90s on a Macintosh SE/30 (with
Gambit).
Notes
-----
  All R4RS syntactic forms are defined, including `delay'.  Along with
`delay' are simple definitions for `make-promise' (into which `delay'
expressions expand) and `force'.
  `syntax-rules' and `with-syntax' (described in TR356) are defined.
  `syntax-case' is actually defined as a macro that expands into calls
to the procedure `syntax-dispatch' and the core form `syntax-lambda';
do not redefine these names.
  Several other top-level bindings not documented in TR356 are created:
   * the "hooks" in `hooks.ss'
   * the `build-' procedures in `output.ss'
   * `expand-syntax' (the expander)
  The syntax of define has been extended to allow `(define ID)', which
assigns ID to some unspecified value.
  We have attempted to maintain R4RS compatibility where possible.  The
incompatibilities should be confined to `hooks.ss'.  Please let us know
if there is some incompatibility that is not flagged as such.
  Send bug reports, comments, suggestions, and questions to Kent Dybvig
([e-mail]).
File: slib.info,  Node: Procedures,  Next: Standards Support,  Prev: Macro Implementations,  Up: Top
Procedures
**********
  Anything that doesn't fall neatly into any of the other categories
winds up here.
* Menu:
* Bit-Twiddling::               'logical
* Common List Functions::       'common-list-functions
* Format::                      'format
* Generic-Write::               'generic-write
* Line I/O::                    'line-i/o
* Modular Arithmetic::          'modular
* Multi-processing::            'process
* Object-To-String::            'object->string
* Plotting::                    'charplot
* Pretty-Print::                'pretty-print, 'pprint-file
* Prime Factorization::         'prime
* Random Numbers::              'random
* Sorting::                     'sort
* Standard I/O::                'stdio
* String-Case::                 'string-case
* String Ports::                'string-port
* Tektronix Graphics Support::
File: slib.info,  Node: Bit-Twiddling,  Next: Common List Functions,  Prev: Procedures,  Up: Procedures
Bit-Twiddling
=============
  `(require 'logical)'
  The bit-twiddling functions are made available through the use of the
`logical' package.  `logical' is loaded by inserting `(require
'logical)' before the code that uses these functions.
 -- Function: logand N1 N1
     Returns the integer which is the bit-wise AND of the two integer
     arguments.
     Example:
          (number->string (logand #b011 #b100) 2)
             => "0"
          (number->string (logand #b10111 #b01101) 2)
             => "101"
 -- Function: logior N1 N2
     Returns the integer which is the bit-wise OR of the two integer
     arguments.
     Example:
          (number->string (logior #b10101010 #b01010101) 2)
             => "11111111"
          (number->string (logior #b10000000 #b00000001) 2)
             => "10000001"
 -- Function: logxor N1 N2
     Returns the integer which is the bit-wise XOR of the two integer
     arguments.
     Example:
          (number->string (logxor #b10101010 #b01010101) 2)
             => "11111111"
          (number->string (logxor #b111 #b010) 2)
             => "101"
 -- Function: lognot N
     Returns the integer which is the 2s-complement of the integer
     argument.
     Example:
          (number->string (lognot #b10000000) 2)
             => "-10000001"
          (number->string (lognot #b0) 2)
             => "-1"
 -- Function: ash INT COUNT
     Returns an integer equivalent to `(inexact->exact (floor (* INT
     (expt 2 COUNT))))'.
     Example:
          (number->string (ash #b1 3) 2)
             => "1000"
          (number->string (ash #b1010 -1) 2)
             => "101"
 -- Function: logcount N
     Returns the number of bits in integer N.  If integer is positive,
     the 1-bits in its binary representation are counted.  If negative,
     the 0-bits in its two's-complement binary representation are
     counted.  If 0, 0 is returned.
     Example:
          (logcount #b10101010)
             => 4
          (logcount 0)
             => 0
          (logcount -2)
             => 1
 -- Function: integer-length N
     Returns the number of bits neccessary to represent N.
     Example:
          (integer-length #b10101010)
             => 8
          (integer-length 0)
             => 0
          (integer-length #b1111)
             => 4
 -- Function: integer-expt N K
     Returns N raised to the non-negative integer exponent K.
     Example:
          (integer-expt 2 5)
             => 32
          (integer-expt -3 3)
             => -27
 -- Function: bit-extract N START END
     Returns the integer composed of the START (inclusive) through END
     (exclusive) bits of N.  The STARTth bit becomes the 0-th bit in
     the result.
     Example:
          (number->string (bit-extract #b10101010 0 4) 2)
             => "1010"
          (number->string (bit-extract #b11111111 4 9) 2)
             => "1111"
File: slib.info,  Node: Common List Functions,  Next: Format,  Prev: Bit-Twiddling,  Up: Procedures
Common List Functions
=====================
  `(require 'common-list-functions)'
  The procedures below follow the Common LISP equivalents apart from
optional arguments in some cases.
* Menu:
* List construction::
* Lists as sets::
* Lists as sequences::
* Destructive list operations::
* Non-list Common LISP functions::
* Tree operations::
File: slib.info,  Node: List construction,  Next: Lists as sets,  Prev: Common List Functions,  Up: Common List Functions
List construction
-----------------
 -- Function: identity X
     IDENTITY returns its argument.  (This probably shouldn't be in the
     "list construction" section, since it doesn't construct anything,
     but this is the section that makes the most sense.)
     Example:
          (identity 3)
             => 3
          (identity '(foo bar))
             => (foo bar)
          (map identity LST)
             == (copy-list LST)
 -- Function: make-list K . INIT
     `make-list' creates and returns a list of K elements.  If INIT is
     included, all elements in the list are initialized to INIT.
     Example:
          (make-list 3)
             => (#<unspecified> #<unspecified> #<unspecified>)
          (make-list 5 'foo)
             => (foo foo foo foo foo)
 -- Function: list* X . Y
     Works like `list' except that the cdr of the last pair is the last
     argument unless there is only one argument, when the result is
     just that argument.  Sometimes called `cons*'.  E.g.:
          (list* 1)
             => 1
          (list* 1 2 3)
             => (1 2 . 3)
          (list* 1 2 '(3 4))
             => (1 2 3 4)
          (list* ARGS '())
             == (list ARGS)
 -- Function: copy-list LST
     `copy-list' makes a copy of LST using new pairs and returns it.
     Only the top level of the list is copied, i.e., pairs forming
     elements of the copied list remain `eq?' to the corresponding
     elements of the original; the copy is, however, not `eq?' to the
     original, but is `equal?' to it.
     Example:
          (copy-list '(foo foo foo))
             => (foo foo foo)
          (define q '(foo bar baz bang))
          (define p q)
          (eq? p q)
             => #t
          (define r (copy-list q))
          (eq? q r)
             => #f
          (equal? q r)
             => #t
          (define bar '(bar))
          (eq? bar (car (copy-list (list bar 'foo))))
          => #t
File: slib.info,  Node: Lists as sets,  Next: Lists as sequences,  Prev: List construction,  Up: Common List Functions
Lists as sets
-------------
  `eq?' is used to test for membership by all the procedures below
which treat lists as sets.
 -- Function: adjoin E L
     `adjoin' returns the adjoint of the element E and the list L.
     That is, if E is in L, `adjoin' returns L, otherwise, it returns
     `(cons E L)'.
     Example:
          (adjoin 'baz '(bar baz bang))
             => (bar baz bang)
          (adjoin 'foo '(bar baz bang))
             => (foo bar baz bang)
 -- Function: union L1 L2
     `union' returns the combination of L1 and L2 with duplicates
     removed.
     Example:
          (union '(1 2 3 4) '(5 6 7 8))
             => (4 3 2 1 5 6 7 8)
          (union '(1 2 2 1) '(3 4 1 8))
             => (2 3 4 1 8)
 -- Function: intersection L1 L2
     `intersection' returns all elements that are in both L1 and L2.
     Example:
          (intersection '(1 2 3 4) '(3 4 5 6))
             => (3 4)
          (intersection '(1 2 3 4) '(5 6 7 8))
             => ()
 -- Function: set-difference L1 L2
     `set-difference' returns the union of all elements that are in L1
     but not in L2.
     Example:
          (set-difference '(1 2 3 4) '(3 4 5 6))
             => (1 2)
          (set-difference '(1 2 3 4) '(1 2 3 4 5 6))
             => ()
 -- Function: member-if PRED LST
     `member-if' returns LST if `(PRED ELEMENT)' is `#t' for any
     ELEMENT in LST.  Returns `#f' if PRED does not apply to any
     ELEMENT in LST.
     Example:
          (member-if vector? '(1 2 3 4))
             => #f
          (member-if number? '(1 2 3 4))
             => (1 2 3 4)
 -- Function: some PRED LST . MORE-LSTS
     PRED is a boolean function of as many arguments as there are list
     arguments to `some' i.e., LST plus any optional arguments. PRED is
     applied to successive elements of the list arguments in order.
     `some' returns `#t' as soon as one of these applications returns
     `#t', and is `#f' if none returns `#t'.  All the lists should have
     the same length.
     Example:
          (some odd? '(1 2 3 4))
             => #t

          (some odd? '(2 4 6 8))
             => #f

          (some > '(2 3) '(1 4))
             => #f
 -- Function: every PRED LST . MORE-LSTS
     `every' is analogous to `some' except it returns `#t' if every
     application of PRED is `#t' and `#f' otherwise.
     Example:
          (every even? '(1 2 3 4))
             => #f

          (every even? '(2 4 6 8))
             => #t

          (every > '(2 3) '(1 4))
             => #f
 -- Function: notany PRED . LST
     `notany' is analogous to `some' but returns `#t' if no application
     of PRED returns `#t' or `#f' as soon as any one does.
 -- Function: notevery PRED . LST
     `notevery' is analogous to `some' but returns `#t' as soon as an
     application of PRED returns `#f', and `#f' otherwise.
     Example:
          (notevery even? '(1 2 3 4))
             => #t

          (notevery even? '(2 4 6 8))
             => #f
 -- Function: find-if PRED LST
     `find-if' searches for the first ELEMENT in LST such that `(PRED
     ELEMENT)' returns `#t'.  If it finds any such ELEMENT in LST,
     ELEMENT is returned. Otherwise, `#f' is returned.
     Example:
          (find-if number? '(foo 1 bar 2))
             => 1

          (find-if number? '(foo bar baz bang))
             => #f

          (find-if symbol? '(1 2 foo bar))
             => foo
 -- Function: remove ELT LST
     `remove' removes all occurrences of ELT from LST using `eqv?' to
     test for equality and returns everything that's left. N.B.: other
     implementations (Chez, Scheme->C and T, at least) use `equal?' as
     the equality test.
     Example:
          (remove 1 '(1 2 1 3 1 4 1 5))
             => (2 3 4 5)

          (remove 'foo '(bar baz bang))
             => (bar baz bang)
 -- Function: remove-if PRED LST
     `remove-if' removes all ELEMENTs from LST where `(PRED ELEMENT)'
     is `#t' and returns everything that's left.
     Example:
          (remove-if number? '(1 2 3 4))
             => ()

          (remove-if even? '(1 2 3 4 5 6 7 8))
             => (1 3 5 7)
 -- Function: remove-if-not PRED LST
     `remove-if-not' removes all ELEMENTs from LST for which `(PRED
     ELEMENT)' is `#f' and returns everything that's left.
     Example:
          (remove-if-not number? '(foo bar baz))
             => ()
          (remove-if-not odd? '(1 2 3 4 5 6 7 8))
             => (1 3 5 7)
File: slib.info,  Node: Lists as sequences,  Next: Destructive list operations,  Prev: Lists as sets,  Up: Common List Functions
Lists as sequences
------------------
 -- Function: position OBJ LST
     `position' returns the 0-based position of OBJ in LST, or `#f' if
     OBJ does not occur in LST.
     Example:
          (position 'foo '(foo bar baz bang))
             => 0
          (position 'baz '(foo bar baz bang))
             => 2
          (position 'oops '(foo bar baz bang))
             => #f
 -- Function: reduce P LST
     `reduce' combines all the elements of a sequence using a binary
     operation (the combination is left-associative).  For example,
     using `+', one can add up all the elements.  `reduce' allows you to
     apply a function which accepts only two arguments to more than 2
     objects.  Functional programmers usually refer to this as "foldl".
     `collect:reduce' (*Note Collections::) provides a version of
     `collect' generalized to collections.
     Example:
          (reduce + '(1 2 3 4))
             => 10
          (define (bad-sum . l) (reduce + l))
          (bad-sum 1 2 3 4)
             == (reduce + (1 2 3 4))
             == (+ (+ (+ 1 2) 3) 4)
          => 10
          (bad-sum)
             == (reduce + ())
             => ()
          (reduce string-append '("hello" "cruel" "world"))
             == (string-append (string-append "hello" "cruel") "world")
             => "hellocruelworld"
          (reduce anything '())
             => ()
          (reduce anything '(x))
             => x
     What follows is a rather non-standard implementation of `reverse'
     in terms of `reduce' and a combinator elsewhere called "C".
          ;;; Contributed by Jussi Piitulainen ([e-mail])

          (define commute
            (lambda (f)
              (lambda (x y)
                (f y x))))

          (define reverse
            (lambda (args)
              (reduce-init (commute cons) args)))
 -- Function: reduce-init P INIT LST
     `reduce-init' is the same as reduce, except that it implicitly
     inserts INIT at the start of the list.  `reduce-init' is preferred
     if you want to handle the null list, the one-element, and lists
     with two or more elements consistently.  It is common to use the
     operator's idempotent as the initializer.  Functional programmers
     usually call this "foldl".
     Example:
          (define (sum . l) (reduce-init + 0 l))
          (sum 1 2 3 4)
             == (reduce-init + 0 (1 2 3 4))
             == (+ (+ (+ (+ 0 1) 2) 3) 4)
             => 10
          (sum)
             == (reduce-init + 0 '())
          => 0

          (reduce-init string-append "@" '("hello" "cruel" "world"))
             == (string-append (string-append (string-append "@" "hello") "cruel") "world")
             => "@hellocruelworld"
     Given a differentiation of 2 arguments, `diff', the following will
     differentiate by any number of variables.
          (define (diff* exp . vars)
            (reduce-init diff exp vars))
     Example:
          ;;; Real-world example:  Insertion sort using reduce-init.

          (define (insert l item)
            (if (null? l)
                (list item)
                (if (< (car l) item)
                    (cons (car l) (insert (cdr l) item))
                    (cons item l))))
          (define (insertion-sort l) (reduce-init insert '() l))

          (insertion-sort '(3 1 4 1 5)
             == (reduce-init insert () (3 1 4 1 5))
             == (insert (insert (insert (insert (insert () 3) 1) 4) 1) 5)
             == (insert (insert (insert (insert (3)) 1) 4) 1) 5)
             == (insert (insert (insert (1 3) 4) 1) 5)
             == (insert (insert (1 3 4) 1) 5)
             == (insert (1 1 3 4) 5)
             => (1 1 3 4 5)
 -- Function: butlast LST N
     `butlast' returns all but the last N elements of LST.
     Example:
          (butlast '(1 2 3 4) 3)
             => (1)
          (butlast '(1 2 3 4) 4)
             => ()
 -- Function: nthcdr N LST
     `nthcdr' takes N `cdr's of LST and returns the result.  Thus
     `(nthcdr 3 LST)' == `(cdddr LST)'
     Example:
          (nthcdr 2 '(1 2 3 4))
             => (3 4)
          (nthcdr 0 '(1 2 3 4))
             => (1 2 3 4)
 -- Function: last LST N
     `last' returns the last N elements of LST.  N must be a
     non-negative integer.
     Example:
          (last '(foo bar baz bang) 2)
             => (baz bang)
          (last '(1 2 3) 0)
             => 0
File: slib.info,  Node: Destructive list operations,  Next: Non-list Common LISP functions,  Prev: Lists as sequences,  Up: Common List Functions
Destructive list operations
---------------------------
  These procedures may mutate the list they operate on, but any such
mutation is undefined.
 -- Procedure: nconc ARGS
     `nconc' destructively concatenates its arguments.  (Compare this
     with `append', which copies arguments rather than destroying them.)
     Sometimes called `append!' (*Note Rev2 Procedures::).
     Example:  You want to find the subsets of a set.  Here's the
     obvious way:
          (define (subsets set)
            (if (null? set)
                '(())
                (append (mapcar (lambda (sub) (cons (car set) sub))
                                (subsets (cdr set)))
                        (subsets (cdr set)))))
     But that does way more consing than you need.  Instead, you could
     replace the `append' with `nconc', since you don't have any need
     for all the intermediate results.
     Example:
          (define x '(a b c))
          (define y '(d e f))
          (nconc x y)
             => (a b c d e f)
          x
             => (a b c d e f)
     `nconc' is the same as `append!' in `sc2.scm'.
 -- Procedure: nreverse LST
     `nreverse' reverses the order of elements in LST by mutating
     `cdr's of the list.  Sometimes called `reverse!'.
     Example:
          (define foo '(a b c))
          (nreverse foo)
             => (c b a)
          foo
             => (a)
     Some people have been confused about how to use `nreverse',
     thinking that it doesn't return a value.  It needs to be pointed
     out that
          (set! lst (nreverse lst))
     is the proper usage, not
          (nreverse lst)
     The example should suffice to show why this is the case.
 -- Procedure: delete! ELT LST
 -- Procedure: delete-if! PRED LST
     Destructive versions of `remove' and `remove-if', called `delete'
     and `delete-if' in Common LISP.
     Example:
          (define lst '(foo bar baz bang))
          (delete! 'foo lst)
             => (bar baz bang)
          lst
             => (foo bar baz bang)

          (define lst '(1 2 3 4 5 6 7 8 9))
          (delete-if! odd? lst)
             => (2 4 6 8)
          lst
             => (1 2 4 6 8)
     Some people have been confused about how to use `delete!' or
     `delete-if!', thinking that they dont' return a value.  It needs to
     be pointed out that
          (set! lst (delete! el lst))
     is the proper usage, not
          (delete! el lst)
     The examples should suffice to show why this is the case.
File: slib.info,  Node: Non-list Common LISP functions,  Next: Tree operations,  Prev: Destructive list operations,  Up: Common List Functions
Non-list Common LISP functions
------------------------------
 -- Function: and? . ARGS
     `and?' checks to see if all its arguments are true.  If they are,
     `and?' returns `#t', otherwise, `#f'.  (In contrast to `and', this
     is a function, so all arguments are always evaluated and in an
     unspecified order.)
     Example:
          (and? 1 2 3)
             => #t
          (and #f 1 2)
             => #f
 -- Function: or? . ARGS
     `or?' checks to see if any of its arguments are true.  If any is
     true, `or?' returns `#t', and `#f' otherwise.  (To `or' as `and?'
     is to `and'.)
     Example:
          (or? 1 2 #f)
             => #t
          (or? #f #f #f)
             => #f
 -- Function: atom? OBJECT
     Returns `#t' if OBJECT is not a pair and `#f' if it is pair.
     (Called `atom' in Common LISP.)
          (atom? 1)
             => #t
          (atom? '(1 2))
             => #f
          (atom? #(1 2))   ; dubious!
             => #t
File: slib.info,  Node: Tree operations,  Prev: Non-list Common LISP functions,  Up: Common List Functions
Tree operations
---------------
  These are operations that treat lists a representations of trees.
 -- Function: subst NEW OLD TREE
 -- Function: substq NEW OLD TREE
 -- Function: substv NEW OLD TREE
     `subst' makes a copy of TREE, substituting NEW for every subtree
     or leaf of TREE which is `equal?' to OLD and returns a modified
     tree.  The original TREE is unchanged, but may share parts with
     the result.
     `substq' and `substv' are similar, but test against OLD using
     `eq?' and `eqv?' respectively.
     Examples:
          (substq 'tempest 'hurricane '(shakespeare wrote (the hurricane)))
             => (shakespeare wrote (the tempest))
          (substq 'foo '() '(shakespeare wrote (twelfth night)))
             => (shakespeare wrote (twelfth night . foo) . foo)
          (subst '(a . cons) '(old . pair)
                 '((old . spice) ((old . shoes) old . pair) (old . pair)))
             => ((old . spice) ((old . shoes) a . cons) (a . cons))
 -- Function: copy-tree TREE
     Makes a copy of the nested list structure TREE using new pairs and
     returns it.  All levels are copied, so that none of the pairs in
     the tree are `eq?' to the original ones -- only the leaves are.
     Example:
          (define bar '(bar))
          (copy-list (list bar 'foo))
             => ((bar) foo)
          (eq? bar (car (copy-list (list bar 'foo))))
             => #f